There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return the shortest distance for the ball to stop at the destination. If the ball cannot stop at destination, return -1.
The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).
You may assume that the borders of the maze are all walls (see examples).
Example 1:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4] Output: 12 Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right. The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.
Example 2:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2] Output: -1 Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.
Example 3:
Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1] Output: -1
Constraints:
m == maze.lengthn == maze[i].length1 <= m, n <= 100maze[i][j]is0or1.start.length == 2destination.length == 20 <= startrow, destinationrow <= m0 <= startcol, destinationcol <= n- Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
- The maze contains at least 2 empty spaces.
Average Rating: 4.74 (61 votes)
Solution
Approach #1 Depth First Search [Accepted]
We can view the given search space in the form of a tree. The root node of the tree represents the starting position. Four different routes are possible from each position i.e. left, right, up or down. These four options can be represented by 4 branches of each node in the given tree. Thus, the new node reached from the root traversing over the branch represents the new position occupied by the ball after choosing the corresponding direction of travel.
In order to do this traversal, one of the simplest schemes is to undergo depth first search. We make use of a recursive function dfs for this. From every current position, we try to go as deep as possible into the levels of a tree taking a particular branch traversal direction as possible. When one of the deepest levels is exhausted, we continue the process by reaching the next deepest levels of the tree. In order to travel in the various directions from the current position, we make use of a dirs array. dirs is an array with 4 elements, where each of the elements represents a single step of a one-dimensional movement. For travelling in a particular direction, we keep on adding the appropriate dirs element in the current position till the ball hits a boundary or a wall.
We start with the given start position, and try to explore these directions represented by the dirs array one by one. For every element dir of the dirs chosen for the current travelling direction, we determine how far can the ball travel in this direction prior to hitting a wall or a boundary. We keep a track of the number of steps using count variable.
Apart from this, we also make use of a 2-D distance array. distance[i][j] represents the minimum number of steps required to reach the positon (i,j) starting from the start position. This array is initialized with largest integer values in the beginning.
When we reach any position next to a boundary or a wall during the traversal in a particular direction, as discussed earlier, we keep a track of the number of steps taken in the last direction in count variable. Suppose, we reach the position (i,j) starting from the last position (k,l). Now, for this position, we need to determine the minimum number of steps taken to reach this position starting from the start position. For this, we check if the current path takes lesser steps to reach (i,j) than any other previous path taken to reach the same position i.e. we check if distance[k][l]+count is lesser than distance[i][j]. If not, we continue the process of traversal from the position (k,l) in the next direction.
If distance[k][l]+count is lesser than distance[i][j], we can reach the position (i,j) from the current route in lesser number of steps. Thus, we need to update the value of distance[i][j] as distance[k][l]+count. Further, now we need to try to reach the destination, dest, from the end position (i,j), since this could lead to a shorter path to dest. Thus, we again call the same function dfs but with the position (i,j) acting as the current position.
After this, we try to explore the routes possible by choosing all the other directions of travel from the current position (k,l) as well.
At the end, the entry in distance array corresponding to the destination, dest's coordinates gives the required minimum distance to reach the destination. If the destination can't be reached, the corresponding entry will contain \text{Integer.MAX_VALUE}.
The following animation depicts the process.
Complexity Analysis
-
Time complexity : O(m∗n∗max(m,n)). Complete traversal of maze will be done in the worst case. Here, m and n refers to the number of rows and columns of the maze. Further, for every current node chosen, we can travel upto a maximum depth of max(m,n) in any direction.
-
Space complexity : O(mn). distance array of size m∗n is used.
Approach #2 Using Breadth First Search [Accepted]
Algorithm
Instead of making use of Depth First Search for exploring the search space, we can make use of Breadth First Search as well. In this, instead of exploring the search space on a depth basis, we traverse the search space(tree) on a level by level basis i.e. we explore all the new positions that can be reached starting from the current position first, before moving onto the next positions that can be reached from these new positions.
In order to make a traversal in any direction, we again make use of dirs array as in the DFS approach. Again, whenever we make a traversal in any direction, we keep a track of the number of steps taken while moving in this direction in count variable as done in the last approach. We also make use of distance array initialized with very large values in the beginning. distance[i][j] again represents the minimum number of steps required to reach the position (i,j) from the start position.
This approach differs from the last approach only in the way the search space is explored. In order to reach the new positions in a Breadth First Search order, we make use of a queue, which contains the new positions to be explored in the future. We start from the current position (k,l), try to traverse in a particular direction, obtain the corresponding count for that direction, reaching an end position of (i,j) just near the boundary or a wall. If the position (i,j) can be reached in a lesser number of steps from the current route than any other previous route checked, indicated by distance[k][l]+count<distance[i][j], we need to update distance[i][j] as distance[k][l]+count.
After this, we add the new position obtained, (i,j) to the back of a queue, so that the various paths possible from this new position will be explored later on when all the directions possible from the current position (k,l) have been explored. After exploring all the directions from the current position, we remove an element from the front of the queue and continue checking the routes possible through all the directions now taking the new position(obtained from the queue) as the current position.
Again, the entry in distance array corresponding to the destination, dest's coordinates gives the required minimum distance to reach the destination. If the destination can't be reached, the corresponding entry will contain \text{Integer.MAX_VALUE}.
Complexity Analysis
-
Time complexity : O(m∗n∗max(m,n)). Time complexity : O(m∗n∗max(m,n)). Complete traversal of maze will be done in the worst case. Here, m and n refers to the number of rows and columns of the maze. Further, for every current node chosen, we can travel upto a maximum depth of max(m,n) in any direction.
-
Space complexity : O(mn). queue size can grow upto m∗n in the worst case.
Approach #3 Using Dijkstra Algorithm [Accepted]
Algorithm
Before we look into this approach, we take a quick overview of Dijkstra's Algorithm.
Dijkstra's Algorithm is a very famous graph algorithm, which is used to find the shortest path from any start node to any destination node in the given weighted graph(the edges of the graph represent the distance between the nodes).
The algorithm consists of the following steps:
-
Assign a tentative distance value to every node: set it to zero for our start node and to infinity for all other nodes.
-
Set the start node as current node. Mark it as visited.
-
For the current node, consider all of its neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one to all the neighbors. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.
-
When we are done considering all of the neighbors of the current node, mark the current node as visited. A visited node will never be checked again.
-
If the destination node has been marked visited or if the smallest tentative distance among all the nodes left is infinity(indicating that the destination can't be reached), then stop. The algorithm has finished.
-
Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new current node, and go back to step 3.
The working of this algorithm can be understood by taking two simple examples. Consider the first set of nodes as shown below.
Suppose that the node b is at a shorter distance from the start node a as compared to c, but the distance from a to the destination node, e, is shorter through the node c itself. In this case, we need to check if the Dijkstra's algorithm works correctly, since the node b is considered first while selecting the nodes being at a shorter distance from a. Let's look into this.
-
Firstly, we choose a as the start node, mark it as visited and update the distanceb and distancec values. Here, distancei represents the distance of node i from the start node.
-
Since distanceb<distancec, b is chosen as the next node for calculating the distances. We mark b as visited. Now, we update the distancee value as distanceb+weightbe.
-
Now, c is obviously the next node to be chosen as per the conditions of the assumptions taken above. (For path to e through c to be shorter than path to e through c, distancec<distanceb+weightbe. From c, we determine the distance to node e. Since distancec+weightce is shorter than the previous value of distancee, we update distancee with the correct shorter value.
-
We choose e as the current node. No other distances need to be updated. Thus, we mark e as visited. distancee now gives the required shortest distance.
The above example proves that even if a locally closer node is chosen as the current node first, the ultimate shortest distance to any node is calculated correctly.
Let's take another example to demonstrate that the visited node needs not be chosen again as the current node.
Suppose a is the start node and e is the destination node. Now, suppose we visit b first and mark it as visited, but later on we find that another path exists through c to b, which makes the distanceb shorter than the previous value. But, because of this, we need to consider b as the current node again, since it would affect the value of distancee. But, if we observe closely, such a situation would never occur, because for weightac+weightcb to be lesser than weightab, weightac<weightab in the first place. Thus, b would never be marked visited before c, which contradicts the first assumption. This proves that the visited node needs not be chosen as the current node again.
The given problem is also a shortest distance finding problem with a slightly different set of rules. Thus, we can make use of Dijkstra's Algorithm to determine the minimum number of steps to reach the destination.
The methodology remains the same as the DFS or BFS Approach discussed above, except the order in which the current positions are chosen. We again make use of a distance array to keep a track of the minimum number of steps needed to reach every position from the start position. At every step, we choose a position which hasn't been marked as visited and which is at the shortest distance from the start position to be the current position. We mark this position as visited so that we don't consider this position as the current position again.
From the current position, we determine the number of steps required to reach all the positions possible travelling from the current position(in all the four directions possible till hitting a wall/boundary). If it is possible to reach any position through the current route with a lesser number of steps than the earlier routes considered, we update the corresponding distance entry. We continue the same process for the other directions as well for the current position.
In order to determine the current node, we make use of minDistance function, in which we traverse over the whole distance array and find out an unvisited node at the shortest distance from the start node.
At the end, the entry in distance array corresponding to the destination position gives the required minimum number of steps. If the destination can't be reached, the corresponding entry will contain \text{Integer.MAX_VALUE}.
**Complexity Analysis**-
Time complexity : O((mn)2). Complete traversal of maze will be done in the worst case and function
minDistancetakes O(mn) time. -
Space complexity : O(mn). distance array of size m∗n is used.
Approach #4 Using Dijkstra Algorithm and Priority Queue[Accepted]
Algorithm
In the last approach, in order to choose the current node, we traversed over the whole distance array and found out an unvisited node at the shortest distance from the start node. Rather than doing this, we can do the same task much efficiently by making use of a Priority Queue, queue. This priority queue is implemented internally in the form of a heap. The criteria used for heapifying is that the node which is unvisited and at the smallest distance from the start node, is always present on the top of the heap. Thus, the node to be chosen as the current node, is always present at the front of the queue.
For every current node, we again try to traverse in all the possible directions. We determine the minimum number of steps(till now) required to reach all the end points possible from the current node. If any such end point can be reached in a lesser number of steps through the current path than the paths previously considered, we need to update its distance entry.
Further, we add an entry corresponding to this node in the queue, since its distance entry has been updated and we need to consider this node as the competitors for the next current node choice. Thus, the process remains the same as the last approach, except the way in which the pick out the current node(which is the unvisited node at the shortest distance from the start node).
**Complexity Analysis**-
Time complexity : O(mn∗log(mn)). Complete traversal of maze will be done in the worst case giving a factor of mn. Further,
pollmethod is a combination of heapifying(O(log(n))) and removing the top element(O(1)) from the priority queue, and it takes O(n) time for n elements. In the current case,pollintroduces a factor of log(mn). -
Space complexity : O(mn). distance array of size m∗n is used and queue size can grow upto m∗n in worst case.
January 8, 2018 1:04 AM
I'm not sure if the time complexity for Approach #1 is correct. Consider we go from s to t, at first we choose s's neighbor a as the next start point, and we went all the way down to t (s-a-n-t), and we call this path p. When we trace back to s, we then choose s's neighbor b as the next start point, and we may find out that after we go a few steps, we find we reach a node n on path p and the distance we have gone so far is smaller, so we have to update the rest of p util we finally update t (b-n-t). Revisiting could happen O(m * n) times, and the path could be of length O(m * n), should the time complexity be O(mnm*n)?
July 4, 2018 6:42 AM
Hey vinod! Why the BFS solution does not check the position already visited? Is that because the distance needs to be updated? @vinod23
Last Edit: September 23, 2018 3:01 AM
Please discard the last reply (leetcode doesn't allow edit comment : (. Shouldn't you consider the time wasted on visiting the same node multiple times in Approach 2? Also, I think your time complexity for approach 4 is wrong, you still have to find neighbors so the max(m, n) should appear as well, right?
January 15, 2019 12:14 AM
What's the point of using dijkstra for this problem if the edges aren't weighted? Won't that just give us the same result, time complexity, space complexity, as BFS, just with worse code readability?
January 15, 2019 12:56 PM
My simplified version of Dijkstra Algorithm, where I replace the use of dist int array with a boolean array visited which simply keep track of nodes we've visited, which mean that we've already found the shortest path to it
class Solution {
private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int rows = maze.length, cols = maze[0].length;
int s = start[0] * cols + start[1];
int target = destination[0] * cols + destination[1];
Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
boolean[] visited = new boolean[rows * cols];
// length 2 array: first element -> index (1D), 2nd element -> path cost
pq.offer(new int[]{s, 0});
// visited[s] = true;
while (!pq.isEmpty()) {
// Dijkstra algorithm: the time we pop some element from the priroty queue
// we are guaranteed to find the minimum path cost to it
int[] curr = pq.poll();
visited[curr[0]] = true;
if (curr[0] == target) return curr[1];
int currIdx = curr[0], currCost = curr[1];
int r = currIdx / cols, c = currIdx % cols;
for (int[] direction : directions) {
int rr = r, cc = c, num = 0;
while (isValid(rr + direction[0], cc + direction[1], rows, cols, maze)) {
rr += direction[0];
cc += direction[1];
num += 1;
}
if (num == 0) continue;
int next = rr * cols + cc;
if (visited[next]) continue;
pq.offer(new int[]{next, currCost + num});
}
}
return -1;
}
private boolean isValid(int r, int c, int rows, int cols, int[][] maze) {
return r >= 0 && r < rows && c >= 0 && c < cols && maze[r][c] == 0;
}
}
In the second BFS solution, it is possible to visit the same node multiple times.
September 17, 2017 9:49 PM
Shouldn't you consider the time wasted on visiting the same node multiple times in Approach 2? Also, I think your time complexity for approach is wrong, you still have to find neighbors so the max(m, n)/(m + n) should appear as well, right?
November 27, 2018 1:25 PM
For the BFS approach, why is the time complexity of Maze 1 O(mn) and for Maze 2 its O(mn*max(m, n)).
Can someone please clarify?
Last Edit: October 14, 2018 6:22 PM
My implementation of Dijkstra + PriorityQueue is as below, and I think it more understandable :
private final static int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int[][] minDist = new int[maze.length][maze[0].length];
for (int[] row : minDist) {
Arrays.fill(row, Integer.MAX_VALUE);
}
minDist[start[0]][start[1]] = 0;
dijkstra(minDist, start, maze);
return minDist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : minDist[destination[0]][destination[1]];
}
private static void dijkstra(int[][] minDist, int[] start, int[][] maze) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
pq.offer(new int[]{start[0], start[1], 0});
while (!pq.isEmpty()) {
int[] minVer = pq.poll();
// if (minDist[minVer[0]][minVer[1]] < minVer[2]) {
// continue;
// }
for (int[] dir : directions) {
int nx = minVer[0];
int ny = minVer[1];
int curDist = 0;
while (nx + dir[0] >= 0 && ny + dir[1] >= 0 && nx + dir[0] < minDist.length && ny + dir[1] < minDist[0].length && maze[nx + dir[0]][ny + dir[1]] == 0) {
nx += dir[0];
ny += dir[1];
curDist++;
}
if (minDist[minVer[0]][minVer[1]] != Integer.MAX_VALUE && minDist[nx][ny] > minDist[minVer[0]][minVer[1]] + curDist) {
minDist[nx][ny] = minDist[minVer[0]][minVer[1]] + curDist;
pq.offer(new int[]{nx, ny, minDist[nx][ny]});
}
}
}
}
xxxxxxxxxx};class Solution {public: int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) { int m = maze.size(); int n = maze[0].size(); vector<int> dirs = {0, 1, 0, -1, 0}; vector<vector<int>> distance(m, vector<int>(n, INT_MAX)); queue<vector<int>> q; q.push(start); distance[start[0]][start[1]] = 0; while(!q.empty()) { int size = q.size(); while(size--) { vector<int> curr = q.front(); q.pop(); for(int i=0;i<4;i++) { int x = curr[0] + dirs[i]; int y = curr[1] + dirs[i+1]; int currDist = distance[curr[0]][curr[1]]; while(x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == 0) { x += dirs[i]; y += dirs[i+1]; currDist++; } x -= dirs[i]; y -= dirs[i+1]; if(currDist < distance[x][y]) { distance[x][y] = currDist; q.push({x, y}); } } } } return distance[destination[0]][destination[1]] == INT_MAX ? -1 : distance[destination[0]][destination[1]];